perm filename WINGED[00,BGB] blob
sn#115053 filedate 1974-08-20 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00013 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00003 00002 {F1F2F3⊂C<NαWINGED EDGE.λ30P16I425,0JCFA} SECTION 2.
C00006 00003 {H7O0,630,700
C00008 00004 ⊂2.1 Winged Edge Link Fields.⊃
C00012 00005
C00016 00006 {Q}⊂2.2 Sequential Accessing.⊃
C00019 00007 ⊂2.3 Perimeter Accessing.⊃
C00027 00008 ⊂2.4 Basic Polyhedron Synthesis.⊃
C00029 00009 <Node Makers and Killers>. The MKNODE and KLNODE are the raw
C00034 00010 ⊂2.4 Edge and Face Splitting.⊃
C00040 00011 {O0,0,450L0,255FCJC} FIGURE 2.3 - ESPLIT AND KLEV.{
C00044 00012 {O0,630,450L0,255FCJC} FIGURE 2.4 - MKFE AND KLFE.{
C00049 00013 ⊂2.5 Coordinate Free Polyhedron Representation.⊃
C00052 ENDMK
C⊗;
{F1;F2;F3;⊂C;<N;αWINGED EDGE.;λ30;P16;I425,0;JC;FA} SECTION 2.
{JC;FD} THE WINGED EDGE POLYHEDRON REPRESENTATION.
{λ10;W250;JA;FA}
2.0 Introduction to the Winged Edge.
2.1 Winged Edge Link Fields.
2.2 Sequential Accessing.
2.3 Perimeter Accessing.
2.4 Basic Polyhedron Synthesis.
2.5 Edge and Face Splitting.
2.6 Coordinate Free Polyhedron Representation.
{λ30;W0;I950,0;JU}
⊂2.0 Introduction to the Winged Edge.⊃
In this chapter, a particular computer representation for
polyhedra is presented and some of its virtues and faults are
explained. The representation is implemented as a data structure
composed of small blocks of words containing pointers and data in the
fashion usual to graphics and simulation. An introduction to such
data structures can be found in chapter two of Knuth's Art of
Computer Programming [Knuth]. Quickly reviewing Knuth's terminology,
a node is a group of consecutive words of memory, a field is a named
portion of a node and a link is the absolute machine address of a
node. The notation for referring to a field of a node consists simply
of the field name followed by a link expression enclosed in
parentheses. For example, the two faces of an edge node whoes link is
stored in the variable named "edge", are found in the fields named
NFACE and PFACE, and are referred to as NFACE(edge) and PFACE(edge).
Although my latest language of implementation is PDP-10 machine code,
examples in this chapter will be given in a fictional programming
language which combines ALGOL with Knuthian node/link notation. (As
an exercise, the energetic reader should write out a possible
representation for general polyhedra, before reading any further).
{H7;O0,630,700;
L0,-20,0*5,-61*5;L0,20,0*5,61*5;
L-86*5,83*5,0*5,61*5,86*5,83*5;L-86*5,-83*5,0*5,-61*5,86*5,-83*5;
H2;
L42*5,106*5,86*5,83*5,126*5,0*5,86*5,-83*5,42*5,-106*5,-42*5,-106*5;
L-42*5,-106*5,-86*5,-83*5,-126*5,0*5,-86*5,83*5,-42*5,106*5,42*5,106*5;
L-30,-10;FB }edge
{L-380,-10; }NFACE(edge)
{L240,-10; }PFACE(edge)
{L-70,-370; }NVT(edge)
{L-70,350; }PVT(edge)
{L-360,320; }NCCW(edge)
{L-390,-360; }NCW(edge)
{L220,320; }PCW(edge)
{L260,-360; }PCCW(edge)
{I1300,0;O0,630,950;
λ10;JC;FA} ⊂FIGURE 2.1 - Winged Edge Topology.⊃
The orientation of links is as viewed from the exterior side of the surface.
The eight mnemonics in the figure, were derived as follows:
NFACE(edge) Negative Face of edge.
PFACE(edge) Positive Face of edge.
PVT(edge) Positive Vertex of edge.
NVT(edge) Negative Vertex of edge.
NCW(edge) edge in Negative face Clockwise from edge.
PCW(edge) edge in Positive face Clockwise from edge.
NCCW(edge) edge in Negative face Counter Clockwise from edge.
PCCW(edge) edge in Positive face Counter Clockwise from edge.{λ30;FA}
{Q}
⊂2.1 Winged Edge Link Fields.⊃
A polyhedron in made up of four kinds of nodes: bodies,
faces, edges and vertices. The body node is the head of three rings:
a ring of faces, a ring of edges and a ring of vertices. In this
context, a ring is a doubly linked circular list with a head node.
Each face and each vertex points directly at only one of the edges on
its perimeter. Each edge points at its two faces and its two
vertices. Completing the topology, each edge node contains a link to
each of its four immediate neighboring edges clockwise and counter
clockwise about its face perimeters as seen from the exterior side of
the surface of the polyhedron. These last four links are the wings of
the edge, which provide the basis for efficient face perimeter and
vertex perimeter accessing. Finally, the links of the edge nodes
can be consistently oriented with respect to the surface of the
polyhedron so that the surface always has two sides: the inside and
the outside.
{|;λ10;JA}
BOX 2.1 {JC} WINGED EDGE STRUCTURES AND LINK NAMES.
~Data Structures~ ~Link Names~
1. Face Ring of a Body. NFACE PFACE
2. Edge Ring of a Body. NED PED
3. Vertex Ring of a Body. NVT PVT
4. First Edge of a Vertex. PED
5. First Edge of a Face. PED
6. The two faces of an edge: NFACE PFACE
7. The two vertices of an edge: NVT PVT
8. The four wing edges of an edge: NCW PCW NCCW PCCW
{|;λ30;JU}
Observe that there are twenty-two link fields in the basic
representation: bodies contain six links, faces three links, vertices
three links and edges ten links. If we allow a link name such as PED
to serve different roles depending on whether it applies to a body,
face, edge or vertex; then the minimum number of different link field
names that need to be coined is ten. The data structures and the link
fields comprising the structures are listed in box 2.1 above. The
ten links names include: NFACE and PFACE for two fields that contain
face links in edges and the face ring, NED and PED for two fields
that contain edge links, NVT and PVT for two fields that contain
vertex links, and NCW, PCW, NCCW and PCCW for the four fields that
contain edge links and are called the wings.
By constraining the arrangement of links in an edge node both
the surface orientataion (interior and exterior) and a linear
orientation of the edge as a directed vector can be encoded. Figure
2.1 diagrams the arrangement of the links comprising the topology of
an edge of a polyhedron as viewed from the exterior side of its
surface. Although the vertices in figure 2.1 are shown with only
three edges, vertices may have any number of edges; the other
potential edges would not be directly linked to the middle edge of
the figure and so were not shown.
To complete the representation, space is allocated to contain
the 3-D coordinates of each vertex in fields named XWC, YWC and ZWC;
the initials "WC" stand for <World Coordinates>. For the sake of
vision and display, three more words of space are allocated to hold
the <Perspective Projected coordinates> of each vertex in fields
named XPP, YPP and ZPP. Also a word of thirty six status bits is
carried in every node, permanent status bits specify the type (body,
face, edge, vertex, etc.) of every node, temporary bits provide
space for operations such as hidden line elimination that require
marking bits. Passing now from necessities to conveniences, faces
carry exterior pointing normal vectors and several words of
photometric surface characteristics. The face vectors are derived
from surface topology and vertex loci, and so are not basic
geometric data as in some representations. Bodies carry a print name,
as well as four link fields (DAD, SON, BRO, SIS) for implementing a
parts tree data structure; and two link fields (CW and CCW) for a
body ring of all the bodies in the world model. Node formats are
given in section 11.2 for an implementation based on fixed sized
(twelve word) nodes.
The Winged Edge Polyhedron Representation as just presented
is complete. Edge nodes carry most of the topology, vertex nodes
carry the geometry, face nodes carry the photometry and body nodes
carry the linguistics (nomesclature) and parts tree structure. The
point that remains to be demonstrated, is that the appropriate
subroutines for creating, maintaining and exploiting edge
orientation are easily coded, execute efficiently and provide good
primitives for solving such geometric problems as hidden line
elimination and polyhedral intersection.
{Q}⊂2.2 Sequential Accessing.⊃
An immediate consequence of the ring structures is that the
faces, edges and vertices of a body are sequentially accessible in the
manner illustrated by the following lines of code:
{JA;W0;λ7;F3}
COMMENT APPLY A FUNCTION TO ALL THE FACES, EDGES AND VERTICES OF A BODY;
PROCEDURE APPLY (PROCEDURE FN; INTEGER B);
BEGIN
INTEGER F,E,V;
F ← PFACE(B); DO FN(F) UNTIL B=(F←PFACE(V)); COMMENT APPLY FUNCTION TO FACES OF A BODY;
E ← PED(B); DO FN(E) UNTIL B=(E←PED(E)); COMMENT APPLY FUNCTION TO EDGES OF A BODY;
V ← PVT(B); DO FN(V) UNTIL B=(V←PVT(V)); COMMENT APPLY FUNCTION TO VERTICES OF A BODY;
END;
{JUFA;W0;λ30;}
\The rings could of course have been traversed in the other direction by
invoking NVT, NED and NFACE in place of PVT, PED and PFACE. The reason
for doubly linked list (i.e. rings) is rapid deletion. Finally, observe
that the face and vertex rings could be eliminated at the cost of having
a more complicated face/vertex sequential accessing method requiring a
visitation marking bit in the status word of face and vertex nodes.
The idea might be coded as follows:
{JA;W100;λ7;F3;}
COMMENT APPLY A FUNCTION TO ALL THE FACES OF A BODY WITHOUT USING THE FACE RINGS;
PROCEDURE APPLY (PROCEDURE FN; INTEGER B);
BEGIN
INTEGER F,E,M;
E ← B; COMMENT FIRST EDGE OF BODY;
M ← MARK(PFACE(E)); COMMENT READ INITIAL STATE OF MARKING BIT;
DO FOR F ← PFACE(E),NFACE(E) DO COMMENT FOR BOTH FACES OF EACH EDGE...;
BEGIN
IF M=MARK(F) THEN FN(F); COMMENT APPLY FUNCTION TO "UN-RE-MARKED" FACE;
MARK(F) ← ¬M; COMMENT FLIP THE MARKING BIT;
END;
UNTIL B=(E←PED(E)); COMMENT ALL THE EDGES OF THE BODY;
END;
{JUFA;W0;λ30;}
⊂2.3 Perimeter Accessing.⊃
The perimeter of a face is an ordered list of edges and
vertices, the perimeter of a vertex is an ordered list of edges and
faces, and the perimeter of an edge is an ordered list consisting of
exactly two faces and two vertices. The perimeter definitions are
caricatured in figure 2.2. One virtue of the winged edge
representation is that both vertex and face perimeters can be
traveled in either direction (clockwise or counter clockwise) while
being dynamically maintained in essentially "<one ring>" of nodes.
{O0,630,350;L0,0;H3;FD
L0,-137;C6;L0,-137,0,170;C6;
L-44,10;FD}EDGE{
L-125,-170;FA}An Edge is surrounded{
L-120,-200;FA}by Faces and Vertices{
L0,200;JC;FC} FIGURE 2.2 - Three Kinds of Perimeters.{
L420,170,420-161,52;C6;
L420-161,52,420-100,-137;C6;
L420-100,-137,420+100,-137;C6;
L420+100,-137,420+161,52;C6;
L420+161,52,420,170;C6;
L420-45,-10;FD}FACE{
L420-125,-170;FA}A Face is surrounded{
L420-130,-200;FA}by Edges and Vertices{
L-420,0,-420-161,52;
L-420,0,-420-100,-137;
L-420,0,-420+100,-137;
L-420,0,-420+161,52;
L-420,170,-420,0;C6;
L-420-70,30;FD}VERTEX{
L-420-125,-170;FA}A Vertex is surrounded{
L-420-115,-200;FA}by Edges and Faces{O0,630,950;I590,0;JUFA}
Given one edge of a face (or vertex) perimeter, the next
edge clockwise (or counter clockwise) from the given edge about the
particular face (or vertex) can be retrieved from the data structure
with the assistance of two subroutines called ECW and ECCW. The idea
of the edge clocking routines is to match the given face (or vertex)
with one of the faces (or vertices) of the given edge and to then
return the appropriate wing. A possible coding of ECCW and ECW might
be as follows:
{↓;JA;λ7;F3}
COMMENT FETCH EDGE CCW FROM E ABOUT FV;
INTEGER PROCEDURE ECCW (INTEGER E,FV);
BEGIN "ECCW"
IF PFACE(E)=FV THEN RETURN(PCCW(E));
IF NFACE(E)=FV THEN RETURN(NCCW(E));
IF PVT(E)=FV THEN RETURN(PCW(E));
IF NVT(E)=FV THEN RETURN(NCW(E));
FATAL;
END "ECCW";
{↑;W670;JA;λ7;F3}
COMMENT FETCH EDGE CLOCKWISE FROM E ABOUT FV;
INTEGER PROCEDURE ECW (INTEGER E,FV);
BEGIN "ECW"
IF PFACE(E)=FV THEN RETURN(PCW(E));
IF NFACE(E)=FV THEN RETURN(NCW(E));
IF PVT(E)=FV THEN RETURN(NCCW(E));
IF NVT(E)=FV THEN RETURN(PCCW(E));
FATAL;
END "ECW";
{W0;JUFA;λ30;}
\The first edge of a face or vertex is (of course) immediately
available from the PED field of the face or vertex. For example, the
two procedures below can be used to visit all the edges of a face or
all the edges of a vertex, respectively.
{JA;↓;λ7;F3}
COMMENT APPLY FUNCTION TO EDGES OF A FACE;
PROCEDURE APPLY (PROCEDURE FN; INTEGER F);
BEGIN
INTEGER E,E0;
E←E0←PED(F);
DO FN(E) UNTIL E0=(E←ECCW(E,F));
END;
{↑;W670;JA;λ7;F3}
COMMENT APPLY FUNCTION TO EDGES OF A VERTEX;
PROCEDURE APPLY (PROCEDURE FN; INTEGER V);
BEGIN
INTEGER E,E0;
E←E0←PED(V);
DO FN(E) UNTIL E0=(E←ECCW(E,V));
END;
{JUFA;W0;λ30;}
Using the same idea as in the edge clocking routines, a face
or vertex can be retrieved relative to a given edge and a given face
or vertex. These routines include: FCW and FCCW which return the face
clockwise or counter clockwise from a given edge with respect to a
given vertex; VCW and VCCW which return the vertex clockwise or
counter clockwise from a given edge with respect to a given face; and
OTHER which returns the face or vertex of the given edge opposite the
given face or vertex. Together the seven routines: ECW, ECCW, VCW,
VCCW, FCW, FCCW and OTHER exhaust the possible oriented retrievals
from an edge node; they also alleviate the need to ever explicitly
reference a wing field when traveling the surface of a polyhedron.
With node type checking the primitives can be made stronger, for example
ECCW(vertex,face) is implemented to return the edge counter clockwise
from the given vertex about the given face.
With node type checking and signed arguments the seven perimeter
accessing routines could even be replaced by a single routine perhaps
named PERIMETER_FETCH or PGET. On the other hand, I favor having the
proliferation of accessing names for the sake of documenting the
clocking direction and the types of nodes involved.
Two remaining surface accessing routines, of minor importance,
are BGET(entity) and LINKED(entity,entity). BGET of a face, edge or
vertex merely cycles the appropriate ring to retrieve the body of the
given entity. The LINKED routine determines whether its two
arguments (faces, edges or vertices) are adjacent; there are six
LINKED cases: (i) Face-Face, returns a common edge or FALSE; (ii)
Face-Edge, returns boolean value F=PFACE(E) ∨ F=NFACE(E); (iii)
Edge-Edge, returns a common vertex or false; (v) Edge-Vertex,
returns boolean value V=PVT(E) ∨ V=NVT(E); (vi) Vertex-Vertex,
returns common edge or FALSE. (As in LISP, zero is false and non-zero
is true).
⊂2.4 Basic Polyhedron Synthesis.⊃
{|;λ10;JA}
BOX 2.2 {JC} LOWEST LEVEL WINGED EDGE ROUTINES.
<Node Makers:> MKNODE, MKB, MKF, MKE, MKV, MKTRAM.
<Node Killers:> KLNODE, KLB, KLF, KLE, KLV.
<Wing Mungers:> WING, INVERT, EVERT.
<Surface Fetchers:> ECW, ECCW, OTHER, VCW, VCCW, FCW, FCCW, LINKED.
<Parts Tree Routines:> BDET, BATT, BGET.
{|;λ30;JU}
There are sixteen routines for node creation and link
manipulation which when combined with the nine accessing routines of
the previous section form the nucleus of a polyhedron modeling
system. These routines are very low level in that the final
applications user of winged polyhedra will never need to explicitly
make a node or mung a link. The word <mung> (meaning to alter a link
in place) is LISP slang that deserves to be promoted into the
technical jargon; traditionally, a mung routine is one which makes
applications of the LISP primitives RPLACA and RPLACD. The
twenty five routines listed in box 2.2 are the bedrock
foundation for the Euler primitives developed in chapter three.
<Node Makers and Killers>. The MKNODE and KLNODE are the raw
storage allocation routines which fetch or return a node from the
available free storage. The MKB routine creates a body node with
empty face, edge and vertex rings; the body is placed into the body
ring of the world model. The MKF, MKE and MKV each take one
argument and create a new face, edge or vertex node in the ring of
the given entity; with type checking these three primitives could be
consolidated. Finally the MKTRAM node creates a <tram node>, which
consists of twelve real numbers that represent either a Euclidean
transformation or a Cartesian frame of reference depending on the
context. (Tram nodes are explained in section 3.3). The corresponding
kill routines KLB, KLF, KLE and KLV; remove the entity from its
respectively ring and return its node to free storage.
<Wing Mungers>. The WING(edge1,edge2) routine finds which
face and vertex the arguments edge1 and edge2 have in common and
stores the wing pointers between edge1 and edge2 accordingly.
Recalling that edges are directed vectors, the INVERT(E) routine
flips the direction of an edge by swapping the contents of the
appropriate fields as follows: PFACE(E)↔NFACE(E); PVT(E)↔NVT(E);
NCW(E)↔NCCW(E) and PCW(E)↔PCCW(E). Finally, the EVERT(B) routine
flips the surface orientation of a body, that is turns a body inside
out, by performing the following link swaps on every edge of the
given body: PFACE(E)↔NFACE(E); NCW(E)↔PCCW(E); and NCCW(E)↔PCW(E).
A symetrical but inefficient implentation of WING is as follows:
{JA;λ7;F3;}
PROCEDURE WING(INTEGER E1,E2);
BEGIN
IF PVT(E1)=PVT(E2)∧PFACE(E1)=NFACE(E2)THEN BEGIN PCW(E1)←E2;NCCW(E2)←E1;END;
IF PVT(E1)=PVT(E2)∧NFACE(E1)=PFACE(E2)THEN BEGIN NCCW(E1)←E2; PCW(E2)←E1;END;
IF PVT(E1)=NVT(E2)∧PFACE(E1)=PFACE(E2)THEN BEGIN PCW(E1)←E2;PCCW(E2)←E1;END;
IF PVT(E1)=NVT(E2)∧NFACE(E1)=NFACE(E2)THEN BEGIN NCCW(E1)←E2; NCW(E2)←E1;END;
IF NVT(E1)=PVT(E2)∧PFACE(E1)=PFACE(E2)THEN BEGIN PCCW(E1)←E2; PCW(E2)←E1;END;
IF NVT(E1)=PVT(E2)∧NFACE(E1)=NFACE(E2)THEN BEGIN NCW(E1)←E2;NCCW(E2)←E1;END;
IF NVT(E1)=NVT(E2)∧PFACE(E1)=NFACE(E2)THEN BEGIN PCCW(E1)←E2; NCW(E2)←E1;END;
IF NVT(E1)=NVT(E2)∧NFACE(E1)=PFACE(E2)THEN BEGIN NCW(E1)←E2;PCCW(E2)←E1;END;
END;{λ30;JUFA}
<Part Tree Routines>. As mentioned before, body nodes can be
grouped into a tree structure or parts. The parts tree consumes four
link positions (DAD, SON, BRO, SIS) and is maintained
in body nodes by the
following primitives: BDET(body) detachs a body node from the parts
tree, BATT(body1,body2) attachs body1 to the ring of children
belonging to body2, and BGET(entity) returns the body node at the
head a the given face, edge or vertex ring. At present, the notion of
a body is coincidant with the notion of a simply connect polyhedron;
however by allowing several bodies to be associated with a single polyhedral
surface a flexible object such as an animal could be represented.
⊂2.4 Edge and Face Splitting.⊃
One of the most important properties of the winged edge
representation is that edges and faces can be split using subroutines
that make only local alterations to the data structure; and the
splits can be easily removed (since the doubly linked rings allow
rapid deletion of nodes from a body). The edge split routine, ESPLIT,
makes a new edge and a new vertex and places them into the surface
topology as shown in figure 2.3; the kill edge-vertex routine,
KLEV, undoes an ESPLIT. The face split routine, MKFE, creates a
new edge and a new face and places them into the surface topology as
shown in figure 2.4; the kill face-edge routine, KLFE, undoes a
MKFE.
The rest of this sub section concerns implementation and so
may be skipped by the applications oriented reader. The split and
kill routines are examples of a pattern which applies in coding
operators that alter winged edge structures. In a typical situation,
there are five steps: first, get the proper kinds of nodes into the
body rings using the MKF, MKE, MKV primitives; second, position the
vertices by setting their XWC, YWC, ZWC fields; third, connect each
vertex and face to one of its edges by setting face/vertex PED
fields; fourth, connect each edge to its two faces and its two
vertices by setting the NFACE, PFACE, NVT, PVT fields of the edge;
finally, setup the wing perimeter pointers by applying the WING
primitive to the pairs of edges to be mated.{Q}
{O0,0,450;L0,255;FCJC} FIGURE 2.3 - ESPLIT AND KLEV.{
O0,630-300,450;H4;
L0,0,0,-122;I∂2,∂2;C6; L0,0,0,122;I∂2,∂2;C6;
L-20,-160;FA}NVT{
L-20,140;FA}PVT{
L15,-7;FA}EDGE{
L-200,-12;}NFACE{
L140,-12;}PFACE{
L-172,166,0,122,172,166; L-172,-166,0,-122,172,-166; H2;
L84,212, 172,166,252,0,172,-166,84,-212,-84,-212;
L-84,-212,-172,-166,-252,0,-172,166,-84,212,84,212;
L-200,-240;}BEFORE: VNEW ← ESPLIT(EDGE);{
L-200,-270;}AFTER: EDGE ← KLEV(VNEW);{
O0,630+300,450;H4;
L0,0,0,-122;I∂2,∂2;C6; L0,0,0,122;I∂2,∂2;C6;L2,2;C6;
L-20,-160;FA}NVT{
L-20,140;FA}PVT{
L15,-7;FA}VNEW{
L15,50;FA}ENEW{
L15,-75;FA}EDGE{
L-200,-12;}NFACE{
L140,-12;}PFACE{
L-172,166,0,122,172,166; L-172,-166,0,-122,172,-166; H2;
L84,212, 172,166,252,0,172,-166,84,-212,-84,-212;
L-84,-212,-172,-166,-252,0,-172,166,-84,212,84,212;
L-200,-270;}BEFORE: EDGE ← KLEV(VNEW);{
L-200,-240;}AFTER: VNEW ← ESPLIT(EDGE);{
O0,630,950;
JA;I800,0;↓;λ10;F3}
INTEGER PROCEDURE ESPLIT (INTEGER E);
BEGIN "ESPLIT"
INTEGER VNEW,ENEW,
COMMENT CREATE A NEW EDGE AND VERTEX;
VNEW ← MKV(PVT(E));
ENEW ← MKE(E);
COMMENT CONNECT VERTICES & FACES TO EDGES;
PVT(ENEW) ← PVT(E);
NVT(ENEW) ← VNEW;
PVT(E) ← VNEW;
PFACE(ENEW) ← PFACE(E);
NFACE(ENEW) ← NFACE(E);
COMMENT CONNECT EDGES TO VERTICES;
IF PED(V)=E THEN PED(V)←ENEW;
PED(VNEW)←ENEW;
COMMENT LINK THE WINGS TOGETHER;
NCW(ENEW) ← E; PCCW(ENEW) ← E;
PCW(E) ← ENEW; PCCW(E) ← ENEW;
WING(NCCW(E),ENEW);
WING(PCW(E),ENEW);
RETURN(VNEW);
END "ESPLIT";
{JA;↑;W620;λ10;F3}
INTEGER PROCEDURE KLEV (INTEGER VNEW);
BEGIN "KLEV"
INTEGER E,ENEW,V,F,B;
COMMENT ORIENT EDGES AS IN DIAGRAM;
IF NVT(ENEW) ≠ VNEW THEN INVERT(ENEW);
IF PVT(E) ≠ VNEW THEN INVERT(E);
COMMENT TIE E TO ITS NEW UPPER VERTEX AND WINGS;
V ← PVT(E) ← PVT(ENEW);
WING(PCW(ENEW),E);
WING(NCCW(ENEW),E);
COMMENT ELIMINATE OCCURENCES OF ENEW IN F AND V;
IF PED(V)=ENEW THEN PED(V) ← E;
IF PED(PFACE(E))=ENEW THEN PED(PFACE(E))←E;
IF PED(NFACE(E))=ENEW THEN PED(NFACE(E))←E;
COMMENT REMOVE NODES FROM THEIR RINGS AND RETURN E;
KLV(VNEW);
KLE(ENEW);
RETURN(E);
END "KLEV";
{W0,1260;λ30;JUFA}
The actual routines differ slightly from those given above in
that they do argument type checking and data structure checking;
nevertheless, a diagonostic trace of the implemented version reveals
that the ESPLIT routine executes 170 PDP-10 instructions and the KLEV
routine executes 202 instructions.{Q}
{O0,630,450;L0,255;FCJC} FIGURE 2.4 - MKFE AND KLFE.{
O0,630-300,450;H4;L2,-120;C6;L2,124;C6;
L-15,-160;FA}V2{
L-15,140;FA}V1{
L-20,-7;FA}FACE{
L-172,166,0,122,172,166; L-172,-166,0,-122,172,-166; H2;
L84,212, 172,166,252,0,172,-166,84,-212,-84,-212;
L-84,-212,-172,-166,-252,0,-172,166,-84,212,84,212;
L-200,-240;}BEFORE: ENEW ← MKFE(V1,FACE,V2);{
L-200,-270;}AFTER: FACE ← KLFE(ENEW);{
O0,630+300,450;H4;
L0,0,0,-122;I∂2,∂2;C6;L0,0,0,122;I∂2,∂2;C6;
L-15,-160;FA}V2{
L-15,140;FA}V1{
L-20,-190;FA}NVT{
L-20,170;FA}PVT{
L15,-7;FA}ENEW{
L-200,15;}NFACE{
L-200,-25;}FNEW{
L140,15;}PFACE{
L140,-25;}FACE{
L-172,166,0,122,172,166; L-172,-166,0,-122,172,-166; H2;
L84,212, 172,166,252,0,172,-166,84,-212,-84,-212;
L-84,-212,-172,-166,-252,0,-172,166,-84,212,84,212;
L-200,-270;}BEFORE: FACE ← KLFE(ENEW);{
L-200,-240;}AFTER: ENEW ← MKFE(V1,FACE,V2);{
O0,630,950;JA;λ10;I800,0;↓;F3}
INTEGER PROCEDURE MKFE(INTEGER V1,F,V2);
BEGIN "MKFE"
INTEGER V1,F,V2,FNEW,ENEW,E,E0,B,V;
COMMENT CREATE NEW FACE & EDGE;
FNEW ← MKF(F); ENEW ← MKE(PED(F));
COMMENT LINK NEW EDGES TO ITS FACES & VERTICES;
PED(F) ← PED(FNEW) ← ENEW;
PFACE(ENEW) ← F; NFACE(ENEW) ← FNEW;
PVT(ENEW) ← V1; NVT(ENEW) ← V2;
COMMENT GET THE WINGS OF THE NEW EDGE;
E2 ← PED(V1);
DO E2←ECW((E1←E2),V1) UNTIL FCW(E1,V1)=F;
E4 ← PED(V1);
DO E4←ECW((E3←E4),V2) UNTIL FCW(E3,V2)=F;
COMMENT SCAN CCW FROM V1 REPLACING F'S WITH FNEW;
E ← E2;
DO IF PFACE(E)=F THEN PFACE(E)←FNEW
ELSE NFACE(E)←FNEW;
UNTIL E4 = (E←ECCW(E,FNEW));
COMMENT LINK THE WINGS;
WING(E1,ENEW); WING(E2,ENEW);
WING(E3,ENEW); WING(E4,ENEW);
RETURN(ENEW);
END;
{JA;↑;W635;λ10;F3}
INTEGER PROCEDURE KLFE (INTEGER ENEW);
BEGIN "KLFE"
INTEGER FNEW,V1,V2,E1,E2,E3,E4,E,F,B;
COMMENT PICKUP ALL THE LINKS OF ENEW;
F ← PFACE(ENEW); FNEW ← NFACE(ENEW);
V1 ← PVT(ENEW); V2 ← NVT(ENEW);
E1 ← PCW(ENEW); E2 ← NCCW(ENEW);
E3 ← NCW(ENEW); E4 ← PCCW(ENEW);
COMMENT GET RID OF ENEW APPEARANCES IN F, V1 AND V2;
IF PED(V1) = ENEW THEN PED(V1) ← E1;
IF PED(V2) = ENEW THEN PED(V2) ← E3;
IF PED(F) = ENEW THEN PED(F) ← E3;
COMMENT GET RID OF FNEW APPEARANCES;
E ← E2;
DO IF PFACE(E)=FNEW THEN PFACE(E)←F
ELSE NFACE(E)←F;
UNTIL E4 = (E←ECCW(E,FNEW));
COMMENT LINK WINGS TOGETHER ABOUT F.
WING(E2,E1);WING(E4,E3);
KLF(FNEW);KLE(ENEW);
RETURN(F);
END;
{W0,1260;λ30;JUFA}
Again, the actual routines differ from those given above in that
they do argument type checking and data structure checking. The above two routines
typically take about twice as long to execute as the previous pair; notice
that the execution time is dependent on the length of face perimeters,
which are mostly three or four edges long.
⊂2.5 Coordinate Free Polyhedron Representation.⊃
As in general relativity, all geometric entities can be
represented in a coordinate free form. In particular, the vertex
coordinates of a polyhedra can be recovered from edge lengths and
dihedral angles (the angle formed by the two faces at each edge).
Having the geometry carried by only two numbers per edge rather than
by three numbers per vertex does not necessarily yield a more concise
representation because edges always outnumber vertices two for one,
and in the case of a triangulated polyhedron edges outnumber vertices
by three to one.
One application of a coordinate free representation arises
when it is necessary to measure a shape with simple tools such as a
caliper and straight edge. For example, one way to go about recording
the topology and geometry of an arbitrary object is to draw a
triangulated polyhedron on its surface with serial numbered vertices
and record for each edge its length, its two vertices and its <signed
dihedral length>. The dihedral length is the distance between the
vertices opposite the edge in each of the edge's two triangles, the
length can be given a sign convention to indicate whether the edge is
concave or convex. The required dihedral angles can then be computed
from the signed dihedral lengths.